1004. 最大连续1的个数 III【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 滑动窗口

1. 📝 题目描述

• leetcode

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0，则返回执行操作后 数组中连续 1 的最大个数。

---

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

---

提示：

• 1 <= nums.length <= 10^5
• nums[i] 不是 0 就是 1
• 0 <= k <= nums.length

2. 🎯 s.1 - 滑动窗口

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
  let left = 0
  let zeros = 0
  let res = 0
  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) zeros++
    while (zeros > k) {
      if (nums[left] === 0) zeros--
      left++
    }
    res = Math.max(res, right - left + 1)
  }
  return res
}

• 时间复杂度：$O(n)$，其中 $n$ 是数组的长度
• 空间复杂度：$O(1)$，只使用了常数级别的额外空间

算法思路：

• 维护一个滑动窗口 [left, right]，窗口内最多包含 k 个 0
• 右指针不断右移，遇到 0 时计数器 zeros 加 1
• 当 zeros > k 时，左指针右移缩小窗口，直到窗口内 0 的数量不超过 k
• 每次更新窗口大小的最大值作为结果